function ModAnalysis(ast)
{
  
  function mostRecentInvocationMark(stack)
  {
    for ( var i = 0; i < stack.length; i++)
    {
      var s = stack[i];
      if (s instanceof Cont)
      {
        var marks = s.marks;
        if (marks.length > 0)
        {
          return marks[0];
        }
      }
    }
    return null;
  }

  var e = Object.create(jseval);

  e.memberCont = function(stack, store, time, state, c)
  {
    var mark = mostRecentInvocationMark(stack);
    if (mark !== null)
    {
      var funAddr = mark.funAddr;
      var stringPropertyName = stack[0].user;
      var propertyAccessNode = this.node;
      var baseRef = stack[1];

      var scopeResult = c.e.doScopeLookup(c.l.U_THIS, stack, this.benva, store,
          state, c);
      var as = scopeResult.as;
      state = scopeResult.state;
      if (as.length !== 1)
      {
        throw new Error(as.length + " addresses (!== 1) for this: " + as);
      }
      var ths = as[0];

      baseRef.addresses().forEach(
          function(baseAddress)
          {
            var access = new ModAnalysis.Access(funAddr, ths,
                propertyAccessNode, "read", baseAddress, stringPropertyName,
                store);
            accesses.push(access);
          });
    }
    return jseval.memberCont.call(this, stack, store, time, state, c);
  }

  e.methodOperatorCont = function(stack, store, time, state, c)
  {
    var mark = mostRecentInvocationMark(stack);
    if (mark !== null)
    {
      // print("hey!", stack, this.node);
      var funAddr = mark.funAddr;
      var stringPropertyName = c.l.userLattice
          .abst1(this.node.callee.property.name);
      var propertyAccessNode = this.node.callee;
      var baseRef = stack[0];

      var scopeResult = c.e.doScopeLookup(c.l.U_THIS, stack, this.benva, store,
          state, c);
      var as = scopeResult.as;
      state = scopeResult.state;
      if (as.length !== 1)
      {
        throw new Error(as.length + " addresses (!== 1) for this: " + as);
      }
      var ths = as[0];

      baseRef.addresses().forEach(
          function(baseAddress)
          {
            var access = new ModAnalysis.Access(funAddr, ths,
                propertyAccessNode, "read", baseAddress, stringPropertyName,
                store);
            accesses.push(access);
          });
    }
    return jseval.methodOperatorCont.call(this, stack, store, time, state, c);
  }

  var accesses = [];
  this.ast = ast;
  this.primLattice = new Lattice1();
  var state = new ResultState();
  var jipda = new Jipda({
    lattice : this.primLattice,
    k : 0,
    ag : tagAg,
    evaluator : e
  });
  jipda.evalGlobal(this.ast, {
    state : state
  });
  this.lattice = jipda.lattice;
  this.accesses = accesses;

  function lookupGlobal(name, jsa)
  {
    return jipda.globalStore.lookupAval(
        jipda.globalStore.lookupAval(jipda.globalObject).lookup(
            jsa.primLattice.abst1(name)).addresses[0]).addresses()[0];
  }
  this.globalObjectAs = [];
  this.globalObjectAs = this.globalObjectAs.addEntry(lookupGlobal("Object",
      this), createAst("function Object() {}"));
  this.globalObjectAs = this.globalObjectAs.addEntry(lookupGlobal("Function",
      this), createAst("function Function() {}"));
  this.globalObjectAs = this.globalObjectAs.addEntry(
      lookupGlobal("Array", this), createAst("function Array() {}"));  
}

// //
ModAnalysis.Access = function(funAddr, ths, accessNode, type, baseAddr, name,
    store)
{
  this.funAddr = funAddr;
  this.ths = ths;
  this.accessNode = accessNode;
  this.type = type;
  this.baseAddr = baseAddr;
  this.name = name;
  this.store = store;
}

ModAnalysis.Access.prototype.toString = function()
{
  return "(" + this.funAddr + "," + this.ths + "," + this.accessNode + ","
      + this.type + "," + this.baseAddr + "," + this.name + ", store)";
}

ModAnalysis.Access.prototype.setName =
  function (name)
  {
    return new ModAnalysis.Access(this.funAddr, this.ths, this.accessNode, this.type, this.baseAddr, name, this.store);
  }

//function TypedAccess(funAddr, ths, accessNode, type, baseAddr, name, baseIof,
//    local)
//{
//  this.funAddr = funAddr;
//  this.ths = ths;
//  this.accessNode = accessNode;
//  this.type = type;
//  this.baseAddr = baseAddr;
//  this.name = name;
//  this.baseIof = baseIof;
//  this.local = local;
//}
//
//TypedAccess.prototype.toString = function()
//{
//  return "(" + this.funAddr + "," + this.ths + "," + this.accessNode + ","
//      + this.type + "," + this.baseAddr + "," + this.name + "," + this.baseIof
//      + "," + this.local + ")";
//}
//
function reverseLookup(address, store)
{
  return store.entries.flatMap(function(entry)
  {
    var aval = entry[1].aval;
    if (aval.addresses().memberAt(address) > -1)
    {
      return [ entry[0] ];
    }
    return [];
  });
}

function isPropertyAddress(address)
{
  return address.base instanceof Addr;
}

// function enclosingObject(address, store)
// {
// var ras = reverseLookup(address, store);
// var rasp = ras.filter(isPropertyAddress);
// var raspb = rasp.map(ContextAddr.base);
// return raspb.toSet();
// }

// Addr -> Store -> (Addr -> Store -> Addr*) -> Addr**
function instanceOfStar(addr, store, instanceOf)
{
  var result = [];
  function helper(pref, addr)
  {
    var iofs = instanceOf(addr, store);
    if (iofs.length > 0)
    {
      return iofs.flatMap(function(iof)
      {
        if (Arrays.indexOf(iof, pref, Eq.equals) > -1)
        {
          return [ pref.addLast(addr) ];
        }
        return helper(pref.addLast(addr), iof);
      });
    }
    else
    {
      return [ pref.addLast(addr) ];
    }
  }
  ;
  return helper([], addr);
}

// Addr -> Addr -> Store -> (Addr -> Store -> Addr*) -> bool*
function isLocal(iof, ths, store, instanceOf)
{
  var chains = instanceOfStar(ths, store, instanceOf);
  var local = chains.map(function(chain)
  {
    return Arrays.indexOf(iof, chain, Eq.equals) > -1
  });
  return local.toSet();
}

//function typeAccesses(tras, instanceOf)
//{
//  return tras.flatMap(function(ta)
//  {
//    var baseIofs = instanceOf(ta.baseAddr, ta.store);
//    return baseIofs.flatMap(function(baseIof)
//    {
//      var locals = isLocal(baseIof, ta.ths, ta.store, instanceOf);
//      return locals.map(function(local)
//      {
//        return new TypedAccess(ta.funAddr, ta.ths, ta.accessNode, ta.type,
//            ta.baseAddr, ta.name, baseIof, local);
//      });
//    });
//  });
//}

function filterFunction(funNode, accesses)
{
  return accesses.filter(function(access)
  {
    return access.funAddr.base === funNode.tag;
  });
}

function FunAccess(baseIof, name, local)
{
  this.baseIof = baseIof;
  this.name = name;
  this.local = local;
}
FunAccess.prototype.toString = function()
{
  return "(" + this.baseIof + "," + this.name + "," + this.local + ")";
}
FunAccess.prototype.equals = function(x)
{
  return Eq.equals(this.baseIof, x.baseIof) && this.name.equals(x.name)
      && this.local === x.local;
}

function funAccesses(funNode, trace, instanceOf)
{
  var funTas = filterFunction(funNode, trace);
  var fas = funTas.flatMap(
    function (ta)
    {
      var baseIofs = instanceOf(ta.baseAddr, ta.store);
      return baseIofs.flatMap(
        function (baseIof)
        {
          var locals = isLocal(baseIof, ta.ths, ta.store, instanceOf);
          return locals.map(function (local)
            {
              return new FunAccess(baseIof, ta.name, local);
            })
        })
    })
  return Arrays.deleteDuplicates(fas, Eq.equals);
}

function filterLocal(fas)
{
  return fas.filter(function(access)
  {
    return access.local;
  });
}

function filterForeign(fas)
{
  return fas.filter(function(access)
  {
    return !access.local;
  });
}

function atd(fas)
{
  return fas.length;
}

function atfd(fas)
{
  return filterForeign(fas).length;
}

function atld(fas)
{
  return filterLocal(fas).length;
}

function fdpSet(fas)
{
  return Arrays.deleteDuplicates(filterForeign(fas).map(function(access)
  {
    return access.baseIof;
  }), Eq.equals);
}

function ldpSet(fas)
{
  return Arrays.deleteDuplicates(filterLocal(fas).map(function(access)
  {
    return access.baseIof;
  }), Eq.equals);
}

function fdp(fas)
{
  return fdpSet(fas).length;
}

function laa(fas)
{
  return atld(fas) / atd(fas);
}

// ////////////////
function addrToNode(ast) 
{ 
  return function(address)
    {
      if (isFinite(address.base)) // address directly corresponding to node?
      {
        var tagNode = tagToNode(ast)(address.base);
//        if (isCallExpression(tagNode)) // TODO HACK: should/can(?) be performed in ag 
//        {
//          return tagNode.callee.object;
//        }
        return tagNode;
      }
      return false;
    }
}

function dependencyStar(bs)
{
  var changed = true;
  while (changed)
  {
    changed = false;
    for (var i = 0; i < bs.length - 1; i++)
    {
      var source = bs[i];
      for (var j = i + 1; j < bs.length; j++)
      {
        var target = bs[j];
        var c = source.concat(target).toSet();
        if (c.length !== source.length + target.length)
        {
          changed = true;
          bs = bs.slice(0, i).addLast(c).concat(bs.slice(i+1,j)).concat(bs.slice(j+1));
        }
      }
    }
  }
  return bs;
}

function bucketIndexOf(x, buckets)
{
  for ( var i = 0; i < buckets.length; i++)
  {
    if (Arrays.indexOf(x, buckets[i], Eq.equals) > -1)
    {
      return i;
    }
  }
  return -1;
}

/*
 * type based on [[Prototype]] of object
 */
function protoInstanceOf(address, store)
{
  var object = store.lookupAval(address);
  var protoAddresses = object.Prototype.addresses();
  return protoAddresses;
}

/*
 * type based on [[Prototype]] of object, except for object literals that each get unique type
 */
//function instanceOf2(ast)
//{
//  return function(address, store)
//  {
//    if (isObjectExpression(addrToNode(ast)(address)))
//    {
//      return [ address ];
//    }
//    var object = store.lookupAval(address);
//    var protoAddresses = object.Prototype.addresses();
//    return protoAddresses;
//  }
//}

/*
 * object receives type based on allocation site
 */
function addrInstanceOf(address, store)
{
  return [address];
}

/*
 * object receives type based on allocation site, execept newed objects that get [[Prototype]] as type
 */
function addrProtoInstanceOf(ast)
{ 
  return function (address, store)
    {
      var node = addrToNode(ast)(address);
      if (node)
      {
        if (isNewExpression(node) || isArrayExpression(node) || isCallExpression(node))
        {
          var object = store.lookupAval(address);
          var protoAddresses = object.Prototype.addresses();
          return protoAddresses;
        }
        
      }
      return [address];
    }
}

function bucketInstanceOf(buckets, ast)
{
  return function (address, store)
  {
    var index = bucketIndexOf(address, buckets);
    if (index === -1)
    {
      return addrProtoInstanceOf(ast)(address, store);
    }
    return [index];
  }
}


/*
 * All objects that act as base object for a certain property access are of the
 * same type. Only treats object literals.
 */
//function singleStaticType(tas, ast)
//{
//  var baseToIof = tas.reduce(function(acc, x)
//  {
//    return acc.updateSetEntry(x.accessNode.base, x.baseIof)
//  }, []);
//  // initial buckets are iofs grouped by base node
//  var initialIofBuckets = baseToIof.map(function(biof)
//  {
//    return biof[1];
//  });
//  var iofBuckets = dependencyStar(initialIofBuckets);
//  // print("type buckets", iofBuckets.join("\t"));
//
//  return tas.map(function(ta)
//  {
//    var ol = isObjectLiteralAddr(ta.baseAddr, ast);
//    return new TypedAccess(ta.funAddr, ta.ths, ta.accessNode, ta.type,
//        ta.baseAddr, ta.name, ol ? bucketIndexOf(ta.baseIof, iofBuckets)
//            : ta.baseIof, ta.local);
//  });
//}


function flowsToEq(trace, ast)
{
  var baseNodeToAddr = trace.reduce(
    function (acc, el)
    {
      var address = el.baseAddr;
      var node = addrToNode(ast)(address);
      if (isObjectExpression(node))
      {
        return acc.updateSetEntry(el.accessNode.object, address);
      }
      return acc;
    }, []);
  // initial buckets are baseAddrs of object literals, grouped by baseNode
  var initialAddrBuckets = baseNodeToAddr.map(function (bna) {return bna[1]});
  var addrBuckets = dependencyStar(initialAddrBuckets);
  return addrBuckets;
}

//note: assumes that array prototype is unchanged
function filterArrayAccesses(fas)
{
  return fas.filter(function(fa)
  {
    if (fa.baseIof.toString().equals("Array.prototype@0"))
    {
//      if (lattice.isStringArrayIndex(fa.name))
//      {
//        print("rejecting", fas);
        return false;
//      }
    }
    return true;
  });
}

function mapArrayIndexes(trace, lattice)
{
  return trace.map(
    function(el)
    {
      if (lattice.isStringArrayIndex(el.name))
      {
        return el.setName("IDX"); // 'special' name
      }
      return el;
    });
}

// ////////////////////////////////////

function T1(fun, trace)
{
  var fas = funAccesses(fun, trace, protoInstanceOf);
  return fas;
}

function T2(fun, trace)
{
  var fas = funAccesses(fun, trace, addrInstanceOf);
  return fas;
}

function T3(fun, trace, ast)
{
  var fas = funAccesses(fun, trace, addrProtoInstanceOf(ast));
  return fas;
}

function T4(fun, trace, ast, lattice)
{
  var trace2 = mapArrayIndexes(trace, lattice);
  var fas = funAccesses(fun, trace2, addrProtoInstanceOf(ast));
  return fas;
}

function T5(fun, trace, ast, lattice)
{
  var trace2 = mapArrayIndexes(trace, lattice);
//  var trace3 = 
  var flowsToBuckets = flowsToEq(trace2, ast);
  print("buckets", flowsToBuckets.join("\n"));
  var fas = funAccesses(fun, trace2, bucketInstanceOf(flowsToBuckets, ast));
  return fas;
}

//////////////////////////////////////

//function T2(fun, trace, ast, lattice)
//{
//var fas = funAccesses(fun, trace, instanceOf2(ast));
//var fas2 = filterArrayAccesses(fas, lattice);
//return fas2;
//}
//
//function T3(fun, trace, ast, lattice)
//{
//var sas = singleStaticType(tas, ast, instanceOf2(ast));
//var fas = funAccesses(fun, sas);
//var fas2 = filterArrayAccesses(fas, lattice);
//return fas2;
//}




